import java.util.ArrayList;
import java.util.List;

public class demo1 {
    String[]hash={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> list;
    StringBuilder str;
    public List<String> letterCombinations(String digits) {
        list=new ArrayList<>();
        str=new StringBuilder();
        if(digits.length()==0){
            return list;
        }
        dfs(digits,0);
        return list;
    }
    public void dfs(String digits,int path){
        if(path==digits.length()){
            list.add(str.toString());
            return ;
        }
        String cur=hash[digits.charAt(path)-'0'];
        for(int i=0;i<cur.length();i++){
            str.append(cur.charAt(i));
            dfs(digits,path+1);
            str.setLength(str.length()-1);
        }
    }
}
